Masala #1177

Sizga n, a, b sonlari berilgan. n sonining a factorial darajasi va n sonining b factorial darajasining Eng katta umumiy bo'luvchisini toping. Aniqroq qilib aytadigan bo'lsak quyidagini toping.

                                     EKUB($n^{a!}$,$n^{b!}$) 

Agar yechim juda ham katta bo'lib ketadigan bo'lsa, yechimning 1000000007 ga qoldig'ini chop eting.

Kirish faylining birinchi qatorida T ( 1 ≤ T ≤ $10^5$) - testcaselar soni
Har bir T uchun yagona qatorda a, b, n ( 1 ≤ a, b, n ≤ $10^5$)

Har bir T uchun yagona qatorda yechimni chop eting.